1. Field of the Invention
This invention relates generally to programmable logic devices and more specifically to an architecture for programmable logic devices that is scalable from a low density to a very high density and that includes an input switch matrix, an output switch matrix, and a centralized switch matrix, and provides a fixed, predictable, and deterministic signal propagation time delay.
2. Description of Related Art
A wide variety of PLDs are available for low and medium density logic applications. The main features differentiating the PLDs are speed performance, density, logic flexibility, software complexity required for mapping a user design to the PLD, and effective utilization of resources. Unfortunately, the architecture of many PLDs is not easily scalable to very high densities without sacrificing speed. Typically, each PLD includes a programmable logic array that generates product terms and each macrocell in the PLD is driven by a set of the product terms. The output signal from the macrocell drives a pin of the PLD.
Some PLDs utilize an expander array of product terms to facilitate logic flexibility. Conceptually, the expander array approach attempts to solve product term array logic efficiency with a combination of a "fixed number of product terms" from a logic array and an "allocatable number of product terms" from the expander array. In one approach, each output macrocell has access to a minimum number of product terms from the logic array plus a variable number of product terms that can be borrowed from the expander array. The major advantage of this approach is logic flexibility, because each output macrocell can receive a large number of product terms from the expander array.
However, the expander array method has several major shortcomings. First, the expander array is implemented as either a NAND array or a NOR array. Output lines from the expander array feedback to the input lines of each logic array thereby increasing the number of logic array input lines significantly. Second, the expander array is driven from the same input lines as the input lines to the logic array. Hence, both the expander array and the logic array have a large number of input lines and as the number of product terms in the logic array increases, the number of input lines to both arrays increases.
As the number of input lines to a product term array increases, the silicon die size of the PLD increases and the speed performance of the PLD decreases. Consequently, the expander array approach increases product flexibility at the expense of both speed performance and die size. However, at some point, as the architecture is scaled to larger and larger densities, the array size becomes prohibitive as does the speed performance. Therefore, the application of the expander array concept to very high performance high density PLDs is questionable.
To alleviate software complexity and to facilitate signal routability, some PLDs include a full-cross point programmable interconnect array (PIA) to interconnect the programmable logic blocks in the PLD. The full crosspoint programmable interconnect array approach has the potential advantage of 100% global connectivity for all signals. All global signals are typically brought into a centralized interconnect array and the input signals for each programmable logic block in the PLD are generated from the centralized interconnect array.
Although the number of input signals for each programmable logic block is a subset of the total number of global signals, each input signal can essentially be a function of all global signal sources at the same time. This global connectivity provides 100% connectivity and somewhat simplifies the "Routing" software. Also, since full global connectivity is always available, the routing software is not required to make any particularly complex intelligent decisions for routing signals.
The major disadvantages of the centralized PIA approach are speed degradation, silicon die size, scalability with increased density, and wasting resources. A PLD incorporating a full cross-point programmable interconnect array tends to be (and is likely to be) slower and more expensive than a comparable PLD with a sparsely populated switch matrix. Since the PIA receives feedback signals from all the internal logic macrocells of all logic blocks and all I/O pin feedback signals, the number of input signals to the PIA is directly proportional to the total number and size of the logic blocks, and the number of I/O pins in the PLD. The size of the PIA increases almost exponentially with an increase in PLD density. Very large programmable interconnect arrays are inherently "slow" and have the additional overhead of larger die area.
Considering these limitations, it is not surprising that the PIA has been utilized primarily in smaller density PLDs or high density PLDs with low performance. As the density is increased to larger pin-count and higher-density logic, the PIA overhead becomes quite significant. While conceptually the same approach can be used for larger density devices, in reality the approach becomes very difficult to implement. Therefore, scalability to higher performance higher densities using the full crosspoint PIA approach is questionable.
The last but not the least significant drawback of the PIA is its potential wastage of significant resources. Since the PIA is a monolithic array, it tends to result in significant wastage of resources. The number of input signals needed are usually significantly smaller than the device's full capability. As a result, most of the signal paths remain unutilized.
An alternative to the PIA in segmented block based PLDs is the multiplexer based, sparse switch matrix structure. While the PIA approach strives for flexibility via a brute force approach of throwing silicon at the problem, the multiplexer based sparse switch matrix approach focuses on optimized routability, speed, and die size in a more intelligent manner. Two of the most important parameters for a multiplexer based switch matrix are the number of input lines to each programmable logic block from the switch matrix and the multiplexer size. As the multiplexer size and the number of programmable logic block input lines increase, signal routability increases. Unfortunately, both a larger number of input lines and a larger multiplexer structure also result in slower performance and bigger die sizes.
In a prior art device with a 15 nanosecond (ns) pin-to-pin signal delay, twenty-two to twenty-six programmable logic block input lines and a 16:1 multiplexer based switch matrix were adequate for gate densities up to 3,000 to 3,600 gate equivalents. Twenty-six input lines and a 16:1 multiplexer provide the ability to select the twenty-six programmable logic block input signals from a maximum of 416 different signals.
For higher density PLDs with a sparse switch matrix, each signal had at least 2.5 ways to enter each programmable logic block. For a maximum of 416 different signals and 2.5 ways of routability for each different signal, the number of different input signals is limited to about 152 signals (i.e., 416/2.5).
If the PLD has more than this number of signals, signals must be judiciously selected and routed to achieve "optimal global" connectivity. However, with only a routability factor of 2.5, as the density of the PLD increases signal routing becomes increasingly more difficult.
The major advantage of this single tiered multiplexer-based switch matrix structure (up to certain number of input lines and multiplexer size) is speed and die size. The signal propagation delay through a 16:1 multiplexer, depending on the implementation, is typically about 1 to 2 nanoseconds (ns). This delay is always fixed and depending upon the structure of the switch matrix can be the same for all signals. Further, since all the signals always pass through the switch matrix in a similar manner, the timing delay calculation is relatively simple and straight forward.
While simplicity, speed, and smaller die size are the major advantages of the multiplexer based switch matrix structure, the limitations can be programmable logic block input lines and multiplexer size. Input lines and multiplexer size limitations are related to the density or pin-count of the PLD. A programmable logic block with twenty-six input lines and 16:1 multiplexer for each input line is adequate for a density up to 3,600 gates in a 84-pin package. As the pin-count or the logic density is increased, providing optimal global connectivity with the limitation of twenty-six input lines and a 16:1 multiplexer is difficult. Consequently, a multiplexer-based single tier single switch matrix by itself is also limited in scalability to higher densities.
Another significant problem with the higher density PLDs is associated with the use of the PLD on a circuit board. Typically, the user logic design is programmed into the PLD and a specific signal pin-out for the PLD is obtained. This signal pin-out is used to lay out the circuit board. Frequently, in the testing of the circuit board, it is discovered that the PLD must be reprogrammed to accommodate design changes.
In reprogramming the PLD, assuring that signal pin-out does not change is often quite difficult. Thus, reprogramming the PLD may mean starting over with the circuit board design. This delays development and increases development costs significantly. Thus, the architectures of prior art PLDs are not sufficiently flexible once a signal pin-out for the PLD is established.